1. Description of the Related Art
Locks, which provide mutual exclusion for access to shared resources and/or execution of critical sections of code, are an important and common structuring mechanism for thread-safe concurrent programming. In a multiprocessor environment with threads and preemptive scheduling, threads can participate in a mutual exclusion protocol through the use of lock or “mutex” constructs. In general, a lock is either in locked or unlocked state and only one thread may hold or own the lock at any one time. For example, a thread that owns a lock may be permitted to enter a critical section protected by the lock. If a second thread attempts to obtain ownership of a lock while a first thread holds the lock, the second thread will not be permitted to proceed into the critical section until the first thread releases the lock and the second thread successfully claims ownership of the lock.
A rich variety of lock implementations may be found in current literature. In general, when a lock is not available, a thread can either spin (e.g., repeatedly polling its value while waiting for it to become available) or de-schedule itself, voluntarily making itself ineligible to be dispatched by the operating system's scheduler. The latter is useful if other threads might be eligible to run. An extremely simple “test-and-set” spin lock implementation will simply loop, attempting to use an atomic instruction to change a memory word from an unlocked state to a locked state. With such a simple spin lock, since all contending threads spin on the same lock variable, this technique is said to use “global spinning”. Other more “polite” forms of global spinning, such as “test-and-test-and-set” (TATAS) are possible. While simple, such locks, when contended, generate significant cache coherence traffic and impair the performance of a system by saturating the interconnect from write coherence cache misses. In addition these simple spin locks do not provide FIFO (first-in-first-out) ordering.
A ticket lock is an example of simple global spinning lock. A typical ticket lock consists of two words: a ticket variable and a grant variable. Arriving threads atomically fetch-and-increment the ticket variable and then spin, waiting for grant variable to match the value returned by the fetch-and-increment primitive. At that point the thread is said to own the lock and may safely enter the critical section. Upon exiting the critical section the thread releases the lock by advancing the grant field. This can be accomplished with a simple store operation. Advancing the grant field passes the lock to the next entering thread, if any. Unlike the test-and-set lock, the ticket lock provides FIFO ordering.
To avoid the performance issues inherent in global spinning, it can be useful to employ local spinning, where at most one threads spins on a given variable at any one time. This can reduce cache coherence traffic and coherence hot spots. For example, each thread could spin on a thread-specific variable that is marked when the previous owner releases the lock. However, locks that use local spinning typically require special memory management, e.g., for nodes that are added and removed from a queue, where each node represents a contending thread that is spinning on a field within that node or a node adjacent in the queue. With these locks, when a thread releases a lock it marks the location upon which the next thread to take the lock is spinning, handing off ownership. An array-based queue lock avoids the use of such nodes, but each lock instance must contain an array with one slot for each possible thread that might contend concurrently for that lock. In a system with a large number of logical threads, such an array, when conservatively sized, could prove impractical.